package com.shuang.tree30;

public class HasPathSum {

    //递归 前序 中左右处理 目标值到中节点减去结点的值 直到走到叶子节点判断 目标值是否减到零 是说明找到一条路径返回true
    public boolean hasPathSum(TreeNode root, int targetSum) {

        if (root == null){
            return false;
        }

        //中
        targetSum -= root.val;

        //判断是否到达叶子节点
        if (root.left == null && root.right == null){
            return targetSum == 0;
        }

        //左
        if (root.left != null){

            boolean left = hasPathSum(root.left, targetSum);

            if (left){
                return true; //左边找到了提前返回true
            }
        }

        //右
        if (root.right != null){

            boolean right = hasPathSum(root.right, targetSum);

            if (right){
                return true;
            }
        }

        //左右都没找到返回false
        return false;
    }
}
